class GridMaster(object):
    def canMove(self, direction):
        """
        :type direction: str
        :rtype bool
        """

    def move(self, direction):
        """
        :type direction: str
        """

    def isTarget(self):
        """
        :rtype bool
        """


# 超时
# class Solution(object):
#     def findShortestPath(self, master):
#         matrix = {(0, 0): 1}
#         other = {'U': 'D', 'D': 'U', 'L': 'R', 'R': 'L'}
#         self.final = None
#         def dfs(x, y, dist):
#             if master.isTarget():
#                 self.final = (x, y)
#             for d in ['U', 'D', 'L', 'R']:
#                 if d == 'U':
#                     ux, uy = x - 1, y
#                 if d == 'D':
#                     ux, uy = x + 1, y
#                 if d == 'L':
#                     ux, uy = x, y - 1
#                 if d == 'R':
#                     ux, uy = x, y + 1
#                 if (ux, uy) in matrix:
#                     if matrix[(ux, uy)] > dist + 1:
#                         matrix[(ux, uy)] = dist + 1
#                         master.move(d)
#                         dfs(ux, uy, dist + 1)
#                         master.move(other[d])
#                 else:
#                     if master.canMove(d):
#                         matrix[(ux, uy)] = dist + 1
#                         master.move(d)
#                         dfs(ux, uy, dist + 1)
#                         master.move(other[d])
#
#         dfs(0, 0, 0)
#         if not self.final:
#             return -1
#         else:
#            return matrix[self.final]
# 超时
# import copy
# class Solution(object):
#     def findShortestPath(self, master):
#         st = {(0, 0): master}
#         dist = 0
#         now = {(0, 0)}
#         while st:
#             next_st = {}
#             for x, y in st:
#                 if st[(x, y)].isTarget():
#                     return dist
#                 for d in ['U', 'D', 'L', 'R']:
#                     if d == 'U':
#                         ux, uy = x - 1, y
#                     if d == 'D':
#                         ux, uy = x + 1, y
#                     if d == 'L':
#                         ux, uy = x, y - 1
#                     if d == 'R':
#                         ux, uy = x, y + 1
#                     if (ux, uy) not in now and st[(x, y)].canMove(d):
#                         new_machine = copy.deepcopy(st[(x, y)])
#                         new_machine.move(d)
#                         next_st[(ux, uy)] = new_machine
#                         now.add((ux, uy))
#             dist += 1
#             st = next_st
#         return -1

class Solution(object):
    def findShortestPath(self, master):
        now = {(0, 0)}
        other = {'U': 'D', 'D': 'U', 'L': 'R', 'R': 'L'}
        self.final = None
        def dfs(x, y):
            if master.isTarget():
                self.final = (x, y)
            for d in ['U', 'D', 'L', 'R']:
                if d == 'U':
                    ux, uy = x - 1, y
                if d == 'D':
                    ux, uy = x + 1, y
                if d == 'L':
                    ux, uy = x, y - 1
                if d == 'R':
                    ux, uy = x, y + 1
                if (ux, uy) not in now:
                    if master.canMove(d):
                        now.add((ux, uy))
                        master.move(d)
                        dfs(ux, uy)
                        master.move(other[d])
        dfs(0, 0)
        if not self.final:
            return -1
        st = {(0, 0)}
        dist = 0
        a_set = {(0, 0)}
        while st:
            next_st = set()
            for x, y in st:
                if (x, y) == self.final:
                    return dist
                for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if (ux, uy) in now and (ux, uy) not in a_set:
                        next_st.add((ux, uy))
                        a_set.add((ux, uy))
            dist += 1
            st = next_st


